#include<stdio.h>
#include<assert.h>
#include<stdlib.h>


typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
 
BTNode* CreateTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;	 
	
}

void PreOder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOder(root->left);
	PreOder(root->right);

}

void InOder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOder(root->left);
	printf("%d ", root->data);
	InOder(root->right);
	

}

void PostOder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOder(root->left);
	PostOder(root->right);
	printf("%d ", root->data);


}
//
//int size = 0;
//int TreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	++size;
//	TreeSize(root->left);
//	TreeSize(root->right);
//}

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;   
}

int TreeKLevel(BTNode* root, int k)
{
	assert(k > 0);

	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	int leftK = TreeKLevel(root->left, k-1);
	int rightK = TreeKLevel(root->right, k-1);
	return leftK + rightK;


}


int main()
{
	BTNode* root = CreateTree();
	PreOder(root);
	printf("\n");

	InOder(root); 
	printf("\n");

	PostOder(root);
	printf("\n");

	
	printf("Size of the tree: %d\n", TreeSize(root));

	return 0;
}